1. Field of the Invention
The present invention relates to the field of block decoding.
2. Description of the Related Art
Channel encoding or forward error correction (FEC) consists in adding redundancy to information data to be transmitted over a noise-affected channel or to be stored on a medium likely to be damaged, such as a CD-ROM. On reception or reading, the redundant data may be used to retrieve the information data.
With reference to FIG. 1, a typical generic transmission subsystem contains, on the side of the sender 10, a data source 11 (DAT_SRC), followed by a source encoder 12 (SRC_ENC), a channel encoder 13 (CH_ENC), and finally a modulator 14 (MOD). The source encoder 12 compresses the information data (for example, according to one of the MPEG, H264, or other standards) so as to reduce the bit rate of the data to be transmitted. The channel encoder 13 adds redundancy so that, on the side of the receiver 30, the potential errors due to the noise N introduced on the transmission channel 20 may be corrected. The modulator 14 adapts the signal to the transmission channel (for example, satellite transmission channel, radio transmission channel, etc.). On the side of the receiver 30, a demodulator 34 (DEMOD), followed by a channel decoder 33 (CH_DEC) and a source decoder 32 (SRC_DEC), perform operations corresponding to those handled by the modulator 14, the channel encoder 13 and the source encoder 12, respectively. The demodulated and decoded data is then restored to the entity that uses the data 31 (DAT_U).
Among the currently known error correction codes, the block-mode codes consist in adding, to each message of K information bits, a determined number (N-K) of redundancy bits, so as to form code words of N bits.
Typical block-mode channel encoding algorithms include the BCH (Bose-Chaudhuri-Hocquenghem) code, the Hamming code and even the LDPC (Low Density Parity Check) codes.
The LDPC codes are a class of FEC codes invented in 1960 by Robert Gallager, which constitutes an alternative to the Viterbi codes, and to the more recent turbocodes. The first commercial standard prescribing the use of an LDPC code is the DVB-S2 standard, that is, the second generation standard for digital satellite television, published by the ETSI (European Telecommunication Standardization Institute) and incorporated herein in its entirety.
An LDPC encoder processes messages of K information bits, and delivers as output code words of N bits, with N>K. In other words, it adds N-K redundancy bits which are used, on the receiving side, to correct the transmission errors. These N-K bits are called parity bits.
The N-K bits added to each message of K information bits are computed using an H matrix, called parity check matrix. This H matrix has N-K rows and N columns. It contains zeroes and ones, with a small proportion of ones, which is why the codes based on such a parity matrix are called low density parity check codes. For example, the H matrix may contain 48600 rows and 64800 columns, that is K=16200 and N=64800.
With reference to FIG. 2, an N-bit LDPC code word, in which the K low order bits correspond to the information bits and in which the N-K high order bits correspond to the parity bits, satisfies the relation:H×Ct=0  (1)
On the receiver side, the LDPC decoder corrects the errored bits based on the blocks received via the transmission channel. Each block corresponds to a code word sent over the transmission channel. Each bit sent has a corresponding logarithmic likelihood ratio (LLR). Each LLR is encoded on a number m of bits, for example 6 bits.
A block therefore comprises N*m bits, or for example 64800*6 bits.
For a bit d sent for which there is a corresponding signal y received by the LDPC decoder after the addition of a noise on the transmission channel, the LLR ratio of the bit d relative to the signal y is defined by:
      LLR    ⁡          (      y      )        =            LLR      ⁡              (                  d          /          y                )              =          ln      ⁢                        P          ⁡                      (                          d              =                              0                /                y                                      )                                    P          ⁡                      (                          d              =                              1                /                y                                      )                              in which P(d=0/y) is the probability that the bit d sent is equal to 0 according to the value y received, and P(d=1/y) is the probability that the bit d sent is equal to 1 according to the value y received.
The LDPC decoder uses internal metrics, of a number equal to the number of “1” values in the H matrix, and each encoded on a number t of bits. It updates these metrics according to an iterative algorithm.
In an initialization step, each internal metric ejk is assigned the value of the LLR LLRk corresponding to the column of this internal metric.
With reference to FIG. 3, each iteration comprises update steps performed by rows, then update steps performed by columns.
Each update step performed by row consists in determining for each internal metric e3,k a first new value e3,k(1) according to the values of the other internal metrics (e3,1, e3,2, . . . , e3,k+1, . . . , e3,N−1) of the same row. The update step performed by row uses the relation (1).
Each update step performed by column consists in determining for each internal metric, for example e3,k, a second new value e3,k(2) taking into account the first new values of the internal metrics of the same column (e4,k(1)) and the LLR LLRk corresponding to this column.
To decode a received LDPC block, the decoder performs a number of iterations, for example around fifty iterations. Each internal metric converges towards a given value.
The decoded bits, called hard decision bits, are then obtained by adding the internal metrics by column with the received LLRs. For each column, the corresponding LLR LLRk and the values of the internal metrics after, for example, 50 iterations (e3,k(100), e4,k(100)) are summed. The sign of the sum is used to determine, in a decision step, the value of the decoded bit.
In such a decoding method, the values of the LLRs are used in the initialization step, on each iteration and in the decision step.
With reference to FIG. 4, the typical architecture of an LDPC decoder according to the prior art comprises an input memory or channel memory 41 (denoted CH_MEM in FIG. 4), capable of storing a number 2×N of LLRs. More particularly, the memory 41 comprises a first buffer 41a for storing the N LLRs of the block previously received and which is currently being decoded, and a second buffer 41b for storing the N LLRs of a block currently being received.
The LLRs may be supplied in a roughly continuous manner by a demodulator (not shown). The time to decode a block is less than the time separating the start of provision of two blocks, in order to avoid saturating the input memory 41. Now, the shorter the time separating the start of provision of two blocks, the higher the bit rate can be. The time to decode a block is therefore normally close to the time separating the start of provision of two blocks, while being less than this time separating the start of provision of two blocks.
The decoder also includes processing means. In order to speed up the computations associated with decoding, said processing means comprise a bank of P processors 42. These P processors (denoted Proc1 to ProcP in FIG. 4), perform parallel update computations by row and by column. The number P is called the parallelism index.
While the iterative process is being executed, the processors deliver internal metric update values, each encoded on t bits. The internal metrics are stored in a metrics memory 43 (denoted MET_MEM in FIG. 4). The internal metrics stored in the memory 43 are delivered to the bank of processors 42, via a P-channel mixer, such as a barrel shifter device 44 (denoted BS in FIG. 4) in the case of the DVB-S2 standard. The memory 43 is accessible in write and read modes via respective buses of t×P rows.
After the last iteration, the processors 42 also deliver hard decision bits, which take the value “1” or “0” depending on the sign of the sum on the columns of the H matrix and the corresponding LLRs. These hard decision bits are stored temporarily in an output memory, or hard decision memory 45 (denoted HD_MEM in FIG. 4). The capacity of the memory 45 is equal to N, that is, the size in LLRs of an LDPC block.
Commonly, the blocks received by a storage device are likely to be of several different sizes.
For example, the received blocks may be long blocks of 64800 LLRs or even short blocks of 16200 LLRs. The long blocks occupy approximately four times more space than the short blocks. The processing time required to decode a long block is approximately four times greater than the time needed to process a short block.
The channel memory must therefore be designed to receive blocks likely to be of two different sizes.
FIG. 6 shows an example of channel memory according to the prior art. FIG. 5 shows an example of timing diagrams, one of the timing diagrams representing the writing of the blocks received into the channel memory and the other timing diagram representing the reading on block decoding. The two figures will be explained together.
At the time T0, a first long block L1 is received and written into a first storage element 61 of a first type. The storage elements of this first type have a size suitable for storing a long block. When the write phase is finished, the first long block L1 is processed for decoding purposes, for example by a BCH or LDPC decoding algorithm.
In this example, this first long block L1 is followed by a first short block S1. This first short block S1 is stored in a first storage element 63 of a second type. The storage elements of this second type have a size suitable for storing a short block. The storage capacity of a storage element of the second type is therefore approximately four times less than the storage capacity of a first storage element of the first type.
If, at the time T2, a second short block S2 is received, it must be stored in a second storage element of the second type 64. At the time T2, the first storage element of the second type 63 is still full. Furthermore, a second storage element of the first type 62 must remain free for the case where this second short block S2 is followed by a long block.
Similarly, assuming that the second short block S2 is followed by two more short blocks (S3, S4), these two short blocks must be stored respectively in two storage elements of the second type (65, 66).
The processing of the first long block L1 ends roughly at the time T5. If at the time T5, a fifth short block S5 is received, it may be stored in one or other of the storage elements of the first type (61, 62).
At least four storage elements of the second type (63, 64, 65, 66) are therefore needed to be able to receive blocks likely to be of two different sizes.
More generally, if the ratio of the block sizes is R, R storage elements of the second type will be needed.
Furthermore, the blocks may be likely to be of more than two different sizes.
For example, the received blocks may be long blocks of 64800 LLRs, short blocks of 16200 LLRs, or very short blocks of 8100 LLRs. The channel memory capable of receiving these blocks comprises:
two storage elements of a first type having a size suitable for storing a long block,
four storage elements of a second type having a size suitable for storing a short block, and
eight storage elements of a third type having a size suitable for storing a very short block.
When a bank of P processors is used to perform the decoding computations, and each LLR is encoded on m bits, each storage element (61, 62, 63, 64, 65, 66) is connected to a multiplexer 67 by P*m wires. This gives more than 2000 wires for each storage element given a value of P equal to 360 and a value of m equal to 6. Routing these wires may prove difficult.